home *** CD-ROM | disk | FTP | other *** search
/ Gold Medal Software 3 / Gold Medal Software - Volume 3 (Gold Medal) (1994).iso / prog / word.arj / DRAWTEXP.C < prev    next >
Text File  |  1992-06-27  |  9KB  |  231 lines
  1. /* Draws a bitmap, mapped to a convex polygon (draws a texture-mapped
  2.    polygon). "Convex" means that every horizontal line drawn through
  3.    the polygon at any point would cross exactly two active edges
  4.    (neither horizontal lines nor zero-length edges count as active
  5.    edges; both are acceptable anywhere in the polygon), and that the
  6.    right & left edges never cross. Nonconvex polygons won't be drawn
  7.    properly. Can't fail. */
  8.  
  9. #include <stdio.h>
  10. #include <math.h>
  11. #include "polygon.h"
  12.  
  13. /* Describes the current location and stepping, in both the source and
  14.    the destination, of an edge. Mirrors structure in DRAWTEXP.C. */
  15. typedef struct {
  16.    int Direction;    /* through edge list; 1 for a right edge (forward
  17.                         through vertex list), -1 for a left edge (backward
  18.                         through vertex list) */
  19.    int RemainingScans;  /* height left to scan out in dest */
  20.    int CurrentEnd;      /* vertex # of end of current edge */
  21.    Fixedpoint SourceX;     /* current X location in source for this edge */
  22.    Fixedpoint SourceY;     /* current Y location in source for this edge */
  23.    Fixedpoint SourceStepX; /* X step in source for Y step in dest of 1 */
  24.    Fixedpoint SourceStepY; /* Y step in source for Y step in dest of 1 */
  25.                         /* variables used for all-integer Bresenham's-type
  26.                            X stepping through the dest, needed for precise
  27.                            pixel placement to avoid gaps */
  28.    int DestX;           /* current X location in dest for this edge */
  29.    int DestXIntStep;    /* whole part of dest X step per scan-line Y step */
  30.    int DestXDirection;  /* -1 or 1 to indicate which way X steps
  31.                            (left/right) */
  32.    int DestXErrTerm;    /* current error term for dest X stepping */
  33.    int DestXAdjUp;      /* amount to add to error term per scan line move */
  34.    int DestXAdjDown;    /* amount to subtract from error term when the
  35.                            error term turns over */
  36. } EdgeScan;
  37.  
  38. int StepEdge(EdgeScan *);
  39. int SetUpEdge(EdgeScan *, int);
  40. void ScanOutLine(EdgeScan *, EdgeScan *);
  41. int GetImagePixel(char *, int, int, int);
  42.  
  43. /* Statics to save time that would otherwise be spent passing them to
  44.    subroutines. */
  45. int DestY;
  46. static int MaxVert, NumVerts;
  47. static Point * VertexPtr;
  48. static Point * TexVertsPtr;
  49. char * TexMapBits;
  50. int TexMapWidth;
  51.  
  52. /* Draws a texture-mapped polygon, given a list of destination polygon
  53.    vertices, a list of corresponding source texture polygon vertices, and a
  54.    pointer to the source texture's descriptor. */
  55. void DrawTexturedPolygon(PointListHeader * Polygon, Point * TexVerts,
  56.    TextureMap * TexMap)
  57. {
  58.    int MinY, MaxY, MinVert, i;
  59.    EdgeScan LeftEdge, RightEdge;
  60.  
  61.    NumVerts = Polygon->Length;
  62.    VertexPtr = Polygon->PointPtr;
  63.    TexVertsPtr = TexVerts;
  64.    TexMapBits = TexMap->TexMapBits;
  65.    TexMapWidth = TexMap->TexMapWidth;
  66.  
  67.    /* Nothing to draw if less than 3 vertices */
  68.    if (NumVerts < 3) {
  69.       return;
  70.    }
  71.  
  72.    /* Scan through the destination polygon vertices and find the top of
  73.       the left and right edges, taking advantage of our knowledge that
  74.       vertices run in a clockwise direction (else this polygon wouldn't
  75.       be visible due to backface removal) */
  76.    MinY = 32767;
  77.    MaxY = -32768;
  78.    for (i=0; i<NumVerts; i++) {
  79.       if (VertexPtr[i].Y < MinY) {
  80.          MinY = VertexPtr[i].Y;
  81.          MinVert = i;
  82.       }
  83.       if (VertexPtr[i].Y > MaxY) {
  84.          MaxY = VertexPtr[i].Y;
  85.          MaxVert = i;
  86.       }
  87.    }
  88.  
  89.    /* Reject flat (0-pixel-high) polygons */
  90.    if (MinY >= MaxY) {
  91.       return;
  92.    }
  93.  
  94.    /* The destination Y coordinate is not edge specific; it applies to
  95.       both edges, since we always step Y by 1 */
  96.    DestY = MinY;
  97.  
  98.    /* Set up to scan the initial left and right edges of the source and
  99.       destination polygons. We always step the destination polygon edges
  100.       by one in Y, so calculate the corresponding destination X step for
  101.       each edge, and then the corresponding source image X and Y steps */
  102.    LeftEdge.Direction = -1;   /* set up left edge first */
  103.    SetUpEdge(&LeftEdge, MinVert);
  104.    RightEdge.Direction = 1;   /* set up right edge */
  105.    SetUpEdge(&RightEdge, MinVert);
  106.  
  107.    /* Step down destination edges one scan line at a time. At each scan
  108.       line, find the corresponding edge points in the source image. Scan
  109.       between the edge points in the source, drawing the corresponding
  110.       pixels across the current scan line in the destination polygon. (We
  111.       know which way the left and right edges run through the vertex list
  112.       because visible (non-backface-culled) polygons always have the vertices
  113.       in clockwise order as seen from the viewpoint) */
  114.    for (;;) {
  115.       /* Done if off bottom of clip rectangle */
  116.       if (DestY >= ClipMaxY) {
  117.          return;
  118.       }
  119.  
  120.       /* Draw only if inside Y bounds of clip rectangle */
  121.       if (DestY >= ClipMinY) {
  122.          /* Draw the scan line between the two current edges */
  123.          ScanOutLine(&LeftEdge, &RightEdge);
  124.       }
  125.  
  126.       /* Advance the source and destination polygon edges, ending if we've
  127.          scanned all the way to the bottom of the polygon */
  128.       if (!StepEdge(&LeftEdge)) {
  129.          break;
  130.       }
  131.       if (!StepEdge(&RightEdge)) {
  132.          break;
  133.       }
  134.       DestY++;
  135.    }
  136. }
  137.  
  138. /* Steps an edge one scan line in the destination, and the corresponding
  139.    distance in the source. If an edge runs out, starts a new edge if there
  140.    is one. Returns 1 for success, or 0 if there are no more edges to scan. */
  141. int StepEdge(EdgeScan * Edge)
  142. {
  143.    /* Count off the scan line we stepped last time; if this edge is
  144.       finished, try to start another one */
  145.    if (--Edge->RemainingScans == 0) {
  146.       /* Set up the next edge; done if there is no next edge */
  147.       if (SetUpEdge(Edge, Edge->CurrentEnd) == 0) {
  148.          return(0);  /* no more edges; done drawing polygon */
  149.       }
  150.       return(1);     /* all set to draw the new edge */
  151.    }
  152.  
  153.    /* Step the current source edge */
  154.    Edge->SourceX += Edge->SourceStepX;
  155.    Edge->SourceY += Edge->SourceStepY;
  156.  
  157.    /* Step dest X with Bresenham-style variables, to get precise dest pixel
  158.       placement and avoid gaps */
  159.    Edge->DestX += Edge->DestXIntStep;  /* whole pixel step */
  160.    /* Do error term stuff for fractional pixel X step handling */
  161.    if ((Edge->DestXErrTerm += Edge->DestXAdjUp) > 0) {
  162.       Edge->DestX += Edge->DestXDirection;
  163.       Edge->DestXErrTerm -= Edge->DestXAdjDown;
  164.    }
  165.  
  166.    return(1);
  167. }
  168.  
  169. /* Sets up an edge to be scanned; the edge starts at StartVert and proceeds
  170.    in direction Edge->Direction through the vertex list. Edge->Direction must
  171.    be set prior to call; -1 to scan a left edge (backward through the vertex
  172.    list), 1 to scan a right edge (forward through the vertex list).
  173.    Automatically skips over 0-height edges. Returns 1 for success, or 0 if
  174.    there are no more edges to scan. */
  175. int SetUpEdge(EdgeScan * Edge, int StartVert)
  176. {
  177.    int NextVert, DestXWidth;
  178.    Fixedpoint DestYHeight;
  179.  
  180.    for (;;) {
  181.       /* Done if this edge starts at the bottom vertex */
  182.       if (StartVert == MaxVert) {
  183.          return(0);
  184.       }
  185.  
  186.       /* Advance to the next vertex, wrapping if we run off the start or end
  187.          of the vertex list */
  188.       NextVert = StartVert + Edge->Direction;
  189.       if (NextVert >= NumVerts) {
  190.          NextVert = 0;
  191.       } else if (NextVert < 0) {
  192.          NextVert = NumVerts - 1;
  193.       }
  194.  
  195.       /* Calculate the variables for this edge and done if this is not a
  196.          zero-height edge */
  197.       if ((Edge->RemainingScans =
  198.             VertexPtr[NextVert].Y - VertexPtr[StartVert].Y) != 0) {
  199.          DestYHeight = INT_TO_FIXED(Edge->RemainingScans);
  200.          Edge->CurrentEnd = NextVert;
  201.          Edge->SourceX = INT_TO_FIXED(TexVertsPtr[StartVert].X);
  202.          Edge->SourceY = INT_TO_FIXED(TexVertsPtr[StartVert].Y);
  203.          Edge->SourceStepX = FixedDiv(INT_TO_FIXED(TexVertsPtr[NextVert].X) -
  204.                Edge->SourceX, DestYHeight);
  205.          Edge->SourceStepY = FixedDiv(INT_TO_FIXED(TexVertsPtr[NextVert].Y) -
  206.                Edge->SourceY, DestYHeight);
  207.  
  208.          /* Set up Bresenham-style variables for dest X stepping */
  209.          Edge->DestX = VertexPtr[StartVert].X;
  210.          if ((DestXWidth =
  211.                (VertexPtr[NextVert].X - VertexPtr[StartVert].X)) < 0) {
  212.             /* Set up for drawing right to left */
  213.             Edge->DestXDirection = -1;
  214.             DestXWidth = -DestXWidth;
  215.             Edge->DestXErrTerm = 1 - Edge->RemainingScans;
  216.             Edge->DestXIntStep = -(DestXWidth / Edge->RemainingScans);
  217.          } else {
  218.             /* Set up for drawing left to right */
  219.             Edge->DestXDirection = 1;
  220.             Edge->DestXErrTerm = 0;
  221.             Edge->DestXIntStep = DestXWidth / Edge->RemainingScans;
  222.          }
  223.          Edge->DestXAdjUp = DestXWidth % Edge->RemainingScans;
  224.          Edge->DestXAdjDown = Edge->RemainingScans;
  225.          return(1);  /* success */
  226.       }
  227.       StartVert = NextVert;   /* keep looking for a non-0-height edge */
  228.    }
  229. }
  230.  
  231.